#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int>f(n,1);//代表【0，i-1】乘积
        auto g=f;//g[i]代表【i+1,n-1】的乘积
        for(int i=1;i<n;i++)
        {
            f[i]=f[i-1]*nums[i-1];
        }
        g[n-1]=1;
        for(int i=n-2;i>=0;i--)
        {
            g[i]=g[i+1]*nums[i+1];
        }
        vector<int> ret(nums.size());
        for(int i=0;i<n;i++)
        {
            ret[i]=f[i]*g[i];
        }
        return ret;
    }
};
class Solution1 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> ret(n,1);
        int fprev=1;
        int fcur=1;
        for(int i=1;i<n;i++)
        {
            fcur=fprev*nums[i-1];
            ret[i]*=fcur;
            fprev=fcur;
        }
        fprev=1;
        fcur=1;
        for(int i=n-2;i>=0;i--)
        {
            fcur=fprev*nums[i+1];
            ret[i]*=fcur;
            fprev=fcur;
        }
       
       
        return ret;
    }
};